B+ Tree

基本概念

• 非页节点有 $\lceil n/2\rceil \sim n$ 个子节点，叶节点有 $\lceil (n-1)/2\rceil \sim n-1$ 个值。
• 支持操作：增删查改（具体见 ADS 中 B+ 树的各种操作），复杂度为 $\log N$

Bottom up B+ tree Build

对于一个序列，若要将其构建成 B+ 树，需要经过以下流程

• 对序列进行排序
• 对序列进行划分（根据 B+ 树的支持块大小进行划分）比如对于支持 n=4 的 B+ 树，排序长度为 13 的序列，则划分为 4+4+3+2(最后两块不能是 4+1，因为 $1<\lceil (4-1)/2\rceil$)
• 构建完最底层之后，再从下至上构建
• 写入磁盘（seek 一次，然后顺序写入）

合并 B+ 树

如果要合并两个 B+ 树，流程如下

• 从磁盘中读取 B+ 树的叶子节点（seek 一次，然后顺序读出，因为叶子节点是连续存储的）
• 合并有序序列
• 重复 Bottom up B+ tree build 的操作